package com.leetcode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

/**
 * 797. 所有可能的路径 (中等)
 * <p>
 * 给你一个有n个节点的 有向无环图（DAG），请你找出所有从节点 0到节点 n-1的路径并输出（不要求按特定顺序） 二维数组的第 i
 * 个数组中的单元都表示有向图中 i 号节点所能到达的下一些节点，空就是没有下一个结点了。 译者注：有向图是有方向的，即规定了 a→b
 * 你就不能从 b→a 。
 * <p>
 * 题目理解错误，重点是   <<<二维数组的第 i个数组中的单元都表示有向图中 i 号节点所能到达的下一些节点>>>
 * <<<理解节点的意思，数组里的数字都是节点号，不可能超过二维数组的长度减1，数字不是随意的>>>
 */
public class LeetCode797 {

    public static void main(String[] arg0) {
        int[][] graph = {{4, 3, 1}, {3, 2, 4}, {3}, {4}, {}};
        List<List<Integer>> result = allPathsSourceTarget(graph);
        for (int i = 0; i < result.size(); i++) {
            System.out.println(Arrays.toString(result.get(i).toArray()));
        }
    }

    /**
     * 再做一次，数组里的元素不仅是数字，还是取下一个数字所在行的深度。
     * 例如上面的事例第一行如果选了3，那么下一个数字直接选第四行数组里的，也就是只有4那个。
     * 从数组结构也能看出最大数字是4，二维数组就有五行，第二行不可能有数字1，第三行不可能有数字1和2，以此类推。
     * <p>
     * 方法 -- 深度优先搜索 (双端队列Deque + 递归循环)
     */
    static List<List<Integer>> result = new ArrayList<>();
    static Deque<Integer> stack = new ArrayDeque<>(); // 双端队列，可以控制向对头还是对尾添加或弹出元素，用first和last区分

    public static List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        int start = 0;
        int target = graph.length - 1; // 二维数组行数减1就是目标

        stack.offerLast(start); // 队尾先放入元素0
        dfs(graph, start, target);

        return result;
    }

    public static void dfs(int[][] graph, int lineIndex, int target) {
        if (lineIndex == target) {
            result.add(new ArrayList<>(stack));
            return;
        }

        for (int ele : graph[lineIndex]) {
            stack.offerLast(ele);
            dfs(graph, ele, target);
            stack.pollLast();
        }
    }

    /**
     * 全部错误，题很垃圾
     */
    public static List<List<Integer>> allPathsSourceTargetError(int[][] graph) {
        List<List<Integer>> result = new ArrayList<>();
        int n = graph.length;
        int target = graph[n - 2][0]; // 特别注意没到n-2就到达目标位置的不算
        int start = 0;

        Set<List<Integer>> tmpList = null;
        for (int i = 0; i < n - 1; i++) {
            int[] item = graph[i];
            if (i == 0) {
                tmpList = new HashSet<>();
                for (int j = 0; j < item.length; j++) {
                    if (item[j] <= target) {
                        List<Integer> resItem = new ArrayList<>();
                        resItem.add(start);
                        resItem.add(item[j]);

                        if (item[j] == target) {
                            if (i == (n - 2)) {
                                result.add(resItem);
                            }
                        } else {
                            // 没有结束的先加到临时集合中
                            tmpList.add(resItem);
                        }
                    }
                }
            } else {
                if (tmpList.size() == 0) {
                    break;
                }

                // 再创建一个临时集合
                Set<List<Integer>> newTmpList = new HashSet<>();

                Iterator<List<Integer>> it = tmpList.iterator();
                while (it.hasNext()) {
                    List<Integer> tmpItem = it.next();
                    int lastNum = tmpItem.get(tmpItem.size() - 1);
                    for (int j = 0; j < item.length; j++) {
                        if (item[j] <= target && item[j] > lastNum) {
                            List<Integer> resItem = new ArrayList<>(tmpItem);
                            resItem.add(item[j]);

                            if (item[j] == target) {
                                if (!result.contains(resItem) && i == (n - 2)) {
                                    result.add(resItem);
                                }
                            } else {
                                // 没有结束的先加到新临时集合中
                                newTmpList.add(resItem);
                            }
                        } else if (item[j] == lastNum) {
                            // 没有结束的先加到新临时集合中
                            newTmpList.add(new ArrayList<>(tmpItem));
                        }
                    }
                    it.remove(); // 一定会将原集合tmpList清空
                }
                // 再把新临时集合全部赋值给tmpList
                tmpList = new HashSet<>(newTmpList);
            }
        }

        return result;
    }

}
